فصل 1: منطق و مجموعه ها
فصل 2: ​​رابطه و توابع
فصل 3: اعداد طبیعی
فصل 4 :بخش پذیری و تجزیه به عامل های اول
فصل 5 : languages
فصل 6 : دستگاه های کراندار
فصل 7 :نظریه ماشین ها
فصل 8: ماشین های تورینگ
فصل 9: گروه ها و حساب پیمانه
فصل 10: مقدمه ای بر نظریه کدگذاری
فصل 11: کدهای GROUP
فصل 12: کلید عمومی رمزنگاری
فصل 13: اصل شمول و عدم شمول
فصل 14 : توابع مولد :
فصل15 : معادلات گوناگون
فصل 16 : روابط بازگشتی
فصل 17 : گراف ها
فصل 18 : وزن گراف ها
فصل 19 : الگوریتم های جست و جو
فصل 20 : گراف جهت دار یا direct graph

نام کتاب:Discrete Mathematics
نویسندگان : W W L Chen
انتشار : Macquarie University 2008
فرمت فایل:PDF
زبان کتاب : انگلیسی

برای دانلود هر کدام از فصل های کتاب فقط کافی است بر روی فصل مورد نظر کلیک کنید.

SECTION A --- BASIC MATERIAL

Chapter 1: LOGIC AND SETS

• Sentences
• Tautologies and Logical Equivalence
• Sentential Functions and Sets
• Set Functions
• Quantifier Logic
• Negation

Chapter 2: RELATIONS AND FUNCTIONS

• Relations
• Equivalence Relations
• Equivalence Classes
• Functions

Chapter 3: THE NATURAL NUMBERS

• Introduction
• Induction

Chapter 4: DIVISION AND FACTORIZATION

• Division
• Factorization
• Greatest Common Divisor
• An Elementary Property of Primes

SECTION B --- COMPUTATIONAL ASPECTS

Chapter 5: LANGUAGES

• Introduction
• Regular Languages

Chapter 6: FINITE STATE MACHINES

• Introduction
• Pattern Recognition Machines
• An Optimistic Approach
• Delay Machines
• Equivalence of States
• The Minimization Process
• Unreachable States

Chapter 7: FINITE STATE AUTOMATA

• Deterministic Finite State Automata
• Equivalence of States and Minimization
• Non-Deterministic Finite State Automata
• Regular Languages
• Conversion to Deterministic Finite State Automata
• A Complete Example

Chapter 8: TURING MACHINES

• Introduction
• Design of Turing Machines
• Combining Turing Machines
• The Busy Beaver Problem
• The Halting Problem

Chapter 9: GROUPS AND MODULO ARITHMETIC

• Addition Groups of Integers
• Multiplication Groups of Integers
• Group Homomorphism

Chapter 10: INTRODUCTION TO CODING THEORY

• Introduction
• Improvement to Accuracy
• The Hamming Metric

Chapter 11: GROUP CODES

• Introduction
• Matrix Codes --- An Example
• Matrix Codes --- The General Case
• Hamming Codes
• Polynomials in Z2[X]
• Polynomial Codes

Chapter 12: PUBLIC KEY CRYPTOGRAPHY

• Basic Number Theory
• The RSA Code

SECTION C --- MATHEMATICAL ASPECTS

Chapter 13: PRINCIPLE OF INCLUSION-EXCLUSION

• Introduction
• The General Case
• Two Further Examples

Chapter 14: GENERATING FUNCTIONS

• Introduction
• Some Simple Observations
• The Extended Binomial Theorem

Chapter 15: NUMBER OF SOLUTIONS OF A LINEAR EQUATION

• Introduction
• Case A --- The Simplest Case
• Case B --- Inclusion-Exclusion
• Case C --- A Minor Irritation
• Case Z --- A Major Irritation
• The Generating Function Method

Chapter 16: RECURRENCE RELATIONS

• Introduction
• How Recurrence Relations Arise
• Linear Recurrence Relations
• The Homogeneous Case
• The Non-Homogeneous Case
• The Method of Undetermined Coefficients
• Lifting the Trial Functions
• Initial Conditions
• The Generating Function Method

Chapter 17: GRAPHS

• Introduction
• Valency
• Walks, Paths and Cycles
• Hamiltonian Cycles and Eulerian Walks
• Trees
• Spanning Tree of a Connected Graph

Chapter 18: WEIGHTED GRAPHS

• Introduction
• Minimal Spanning Tree

Chapter 19: SEARCH ALGORITHMS

• Depth-First Search
• Breadth-First Search
• The Shortest Path Problem

Chapter 20: DIGRAPHS

• Introduction
• Networks and Flows
• The Max-Flow-Min-Cut Theorem

شاید در ریاضیات گسسته با مسأله ی زیر برخورد كرده باشید:
مسأله: یك صفحه ی شطرنجی n×n در نظر بگیرید؛ می‌خواهیم با حركت روی خطوط صفحه ی شطرنجی، از نقطه ی A در گوشه ی سمت چپ پائین صفحه، شروع كرده و به نقطه ی B در گوشه ی سمت راست بالای صفحه برسیم. شرط كار این است كه فقط می‌توانیم به سمت‌های راست و بالا حركت كنیم و هرگز نباید به بالای قطر AB برویم. به چند طریق می‌توان از A به B رسید؟....

شاید در ریاضیات گسسته با مسأله ی زیر برخورد كرده باشید:
مسأله: یك صفحه ی شطرنجی n×n در نظر بگیرید؛ می‌خواهیم با حركت روی خطوط صفحه ی شطرنجی، از نقطه ی A در گوشه ی سمت چپ پائین صفحه، شروع كرده و به نقطه ی B در گوشه ی سمت راست بالای صفحه برسیم. شرط كار این است كه فقط می‌توانیم به سمت‌های راست و بالا حركت كنیم و هرگز نباید به بالای قطر AB برویم. به چند طریق می‌توان از A به B رسید؟

طرح این مسأله، انگیزه‌ای برای معرّفی مفاهیم زیر می‌باشد.
تعریف: برای ،n امین عدد كاتالان(ریاضی دان بلژیكی) عبارت است از: .

               E.C.Catalan  

تعریف: همان‌طور كه می‌دانیم هركلمه از تعدادی حرف تشكیل شده است. اگر حرف‌های تشكیل‌دهنده ی كلمات را x و y بگیریم، یك كلمه‌ی Dyck به طول  عبارت است از كلمه‌ای كه از n تا x و n تا y تشكیل شده است و در هیچ قطعه‌ی آغازی كلمه، تعداد yها بیش‌تر از تعداد xها نمی‌باشد.
مثلاً: كلمه‌ی xyyx یك كلمه‌ی Dyck نمی‌باشد چون در قطعه‌ی آغازی xyy تعداد yها از تعداد xها بیش‌‌تر است. امّا xyxyxy یك كلمه‌ی Dyck است.
قرارداد: از این به بعد كلمه‌ی Dyck را با DW و كلمه‌ای كه خاصیّت Dyck ندارد را با NDW نشان می‌دهیم.
مسأله: چند DW به طول  می‌توان نوشت؟
حلّ: تعداد كلّ كلماتی به طول كه می‌توان با n تا x و n تا y نوشت برابر است با .[چرا؟].از طرفی اگر یك NDW دلخواه در نظر بگیریم؛ پس یك قطعه‌ی آغازی از این كلمه وجود دارد كه در آن تعداد yها بیش‌تر از تعداد xها است. اگر اوّلین قطعه‌ی آغازی كه این شرط را دارد در نظر بگیریم و تمامی xهایی كه پس از این قطعه ظاهر می‌شوند را با y و تمامی yها را [در صورت وجود] با x عوض كنیم پس كلمه‌ای با 1-n تا x و 1+n تا y خواهیم داشت [چرا؟].
از طرفی اگر كلمه‌ای دلخواه به طول متشكل از 1-n تا x و 1+n تا y داشته باشیم ،اولین قطعه ی آغازی این كلمه كه تعداد y ها یكی بیش تر از تعداد x هاست در نظر بگیرید و تمامی y هایی كه بعد از این قطعه ظاهر می شوند را با xو تمامی x ها را [در صورت وجود] با y عوض كنید. كلمه‌ی حاصل یك NDW است [چرا؟] .

در واقع این روش یك تناظر یك به یك بین كلماتی به طول شامل 1-n تا x و 1+n تا y و NDWهای به طول  برقرار می‌كند. چون به تعداد كلمه ی به طول شامل 1-n تا x و 1+n تا y داریم ، پس تعداد NDW های به طول  برابر است با . امّا تعداد DWها برابر است با اختلاف تعداد كلّ كلمات و تعداد NDWها، پس :

 تعداد DWهای به طول

اكنون به مسأله‌ای كه در آغاز مقاله مطرح كردیم، برمی‌گردیم.
اگر حركت به سمت راست را با x و حركت به سمت بالا را با y نشان دهیم پس تعداد راه‌های رسیدن از A به B [با توجه به شرط مسأله]برابر است با تعداد DWهای به طول كه همانا  می‌باشد.
مسأله‌ای دیگر: به چند طریق می‌توان با n جفت پرانتز ( )؛ عبارت‌های با معنی نوشت؟
مثلاً برای 3و 2و 1=n داریم:
1=n ( ) .
2=n (( )) و ( ) ( ) .
3=n (( )) ( ) و ( ) (( )) و ( ) ( ) ( ) و ((( ))) و ( ( ) ( ) ) .
اگر به جای )، x و به جای (، y قرار دهیم آن‌گاه تعداد عبارت‌‌های با معنی با n جفت پرانتز با تعداد DWهای به طول برابر خواهد بود و این یعنی برابر است.
تاكنون حلّ سه مسأله منجر به اعداد كاتالان شده است، در ذیل توجّه شما را به دو نمونه ی دیگر جلب می‌كنیم:
الف) تعداد راه‌های مختلف پرانتز‌گذاری بین 1+n نماد ریاضی عبارت است از .
به عنوان مثال اگر a و b و c و d چهار نماد ریاضی باشند، روش‌های مختلف پرانتز‌گذاری بین آن‌ها از این قرار است:

ب) یك 2+n ضلعی محدّب در نظر بگیرید. با وصل كردن رأس‌ها، می‌توان این چند ضلعی را به مثلث‌هایی افراز كرد.
به عنوان مثال برای 3=n داریم :

با توجه به روند مقاله،‌آیا می‌توانید تعداد راه های متفاوت افراز را حدس بزنید؟ بله درست حدس زدید، تعداد روش های متفاوت افراز عبارت است از ‌ .

اعداد كاتالان در مسأله های دیگری از جمله شمارش درخت ها در نظریه گراف یا شمارش نوع خاصی از افراز های مجموعه های متناهی نیز ظاهر می شوند .

برای دانلود اینجا کلیک کنید
 

درسنامه ریاضیات گسسته : برای دانلود کیک کنید(مبحث الگوریتم تقسیم و معادلات خطی با ضرایب واحد)

دانلود